package 牛客.二叉树;

import 剑指offer.TreeNode;

import java.util.ArrayList;

public class BM37二叉搜索树的最近公共祖先 {
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //搜索两个值的路径，进行比较
        ArrayList<Integer> plist=getPath(root,p);
        ArrayList<Integer> qlist=getPath(root,q);

        int res=-1;//来保存最后相同的节点，也就是最近公共祖先！
        for (int i = 0; i <plist.size()&&i<qlist.size() ; i++) {
            int x=plist.get(i);
            int y=qlist.get(i);
            if (x==y) {
                res= x;
            }
        }
        return res;
    }

    private ArrayList<Integer> getPath(TreeNode root, int node) {
        ArrayList<Integer> list=new ArrayList<>();
        TreeNode cur=root;
        while (cur.val!=node) {
            list.add(cur.val);
            if (cur.val>node) {
                cur=cur.left;
            }else {
                cur=cur.right;
            }
        }
        list.add(node);
        return list;
    }

    public int lowestCommonAncestor1 (TreeNode root, int p, int q) {
        // write code here
        //递归实现
        if (root==null) {
            return -1;
        }

        if (root.val>=p && root.val<=q || root.val>=q && root.val<=p) {
            return root.val;
        }

        if (root.val>p && root.val>q) {
            return lowestCommonAncestor(root.left,p,q);
        }else {
            return lowestCommonAncestor(root.right,p,q);
        }

    }
}
